/**
 * 实现 int sqrt(int x) 函数。
 * <p>
 * 计算并返回 x 的平方根，其中 x 是非负整数。
 * <p>
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 4
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: 8
 * 输出: 2
 * 说明: 8 的平方根是 2.82842...,
 *      由于返回类型是整数，小数部分将被舍去
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(mySqrt(8192));
    }

    /**
     * 算出中间值，然后代入
     *
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int i = 0;
        for (; i < 31; i++) {
            if (1 << i >= x) {
                break;
            }
        }
        int z = i / 2;
        int tmp = 1 << z;
        int start;
        int end;
        if (i % 2 == 0) {
            // 此时的目标数范围在2的z次方下，误差为2的z次方/根号2
            start = (int) (0.7 * tmp);
            end = tmp;
        } else {
            // 此时的目标数范围在2的z次方上，误差为2的z次方*根号2
            start = tmp;
            end = (int) (1.42 * tmp);
        }
        int ans = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 算出中间值，然后代入
     *
     * @param x
     * @return
     */
    public static int mySqrt1(int x) {
        if (x == 0) {
            return 0;
        }
        int i = 0;
        for (; i < 31; i++) {
            if (1 << i >= x) {
                break;
            }
        }
        int z = i / 2;
        if (i % 2 == 0) {
            // 如果i是偶数，表示目标数的范围在2的i次方和2的i-1次方内
            for (int j = 1 << z; j > 0; j--) {
                if (j * j <= x) {
                    return j;
                }
            }
        } else {
            // 如果i是奇数，表示目标数的范围在2的i次方和2的i-1次方内
            int j;
            for (j = 1 << z; j <= 46340; j++) {
                if (j * j > x) {
                    return j - 1;
                }
            }
            return 46340;
        }
        return 1;
    }

    /**
     * 算出中间值之后用乘法逼近
     *
     * @param x
     * @return
     */
    public static int mySqrt2(int x) {
        if (x == 0) {
            return 0;
        }
        int i = 0;
        for (; i < 31; i++) {
            if (1 << i >= x) {
                break;
            }
        }
        int z = i / 2;
        if (i % 2 == 0) {
            // 如果i是偶数，表示原值的范围在2的i次方和2的i-1次方内
            // 此时的目标数范围在2的i/2次方下，误差为2的i/2次方/根号2
            if (i >= 5) {
                int tmp = 1 << z;
                int t;
                for (t = 0; t < 4; t++) {
                    tmp = (int) ((double) (10 - t) / 10) * tmp;
                    if (tmp * tmp <= x) {
                        break;
                    }
                }
                for (int j = tmp; j <= 46340; j++) {
                    if (j * j > x) {
                        return j - 1;
                    }
                }
            } else {
                for (int j = 1 << z; j > 0; j--) {
                    if (j * j <= x) {
                        return j;
                    }
                }
            }
        } else {
            // 如果i是奇数，表示原值的范围在2的i次方和2的i-1次方内
            // 此时的目标数范围在2的i/2次方上，误差为2的i/2次方*根号2
            if (i >= 5) {
                int tmp = 1 << z;
                int t;
                for (t = 1; t < 5; t++) {
                    tmp = (int) ((double) (10 + t) / 10) * tmp;
                    if (tmp * tmp > x) {
                        break;
                    }
                }
                if (t == 5) {
                    for (int j = tmp; j <= 46340; j++) {
                        if (j * j > x) {
                            return j - 1;
                        }
                    }
                } else {
                    for (int j = tmp; j > 0; j--) {
                        if (j * j <= x) {
                            return j;
                        }
                    }
                }
                return 46340;
            } else {
                for (int j = 1 << z; j <= 46340; j++) {
                    if (j * j > x) {
                        return j - 1;
                    }
                }
                return 46340;
            }
        }
        return 1;
    }
}